﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0066_Shuffle : IAlgorithm
    {
        // 打乱数组

        // 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

        // 实现 Solution class:
        //  Solution(int[] nums) 使用整数数组 nums 初始化对象
        //  int[] reset() 重设数组到它的初始状态并返回
        //  int[] shuffle() 返回数组随机打乱后的结果

        // 提示：
        //  1 <= nums.length <= 200
        //  -10^6 <= nums[i] <= 10^6
        //  nums 中的所有元素都是 唯一的
        //  最多可以调用 5 * 10^4 次 reset 和 shuffle


        public void Test()
        {
            // 算法参数定义
            var s = new Solution(new int[] { 1, 2, 3 });
            // 算法执行与打印
            foreach (var item in s.Reset())
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            foreach (var item in s.Shuffle())
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            foreach (var item in s.Reset())
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            foreach (var item in s.Shuffle())
            {
                Console.Write(item + " ");
            }
        }

        // 设计问题
        public class Solution
        {
            private int[] Nums;
            private Random Random = new Random();

            public Solution(int[] nums)
            {
                Nums = nums;
            }

            public int[] Reset()
            {
                return Nums;
            }

            public int[] Shuffle()
            {
                if (Nums == null)
                    return null;
                var res = Nums.Clone() as int[];
                for (int j = 1; j < res.Length; j++)
                {
                    int i = Random.Next(0, j + 1);
                    Swap(res, i, j);
                }
                return res;
            }
            private void Swap(int[] a, int i, int j)
            {
                if (i != j)
                {
                    a[i] = a[i] + a[j];
                    a[j] = a[i] - a[j];
                    a[i] = a[i] - a[j];
                }
            }
        }
    }
}
